package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-17 18:04
 **/
public class LeetCodeMianshi0207 {

    /**
     * 使用了两个栈的结构
     * @param headA
     * @param headB
     * @return
     */
    /*public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode temp1 = headA;
        ListNode temp2 = headB;
        //intersection:交点 用来存储两个链表的交点
        ListNode intersection = null;

        Deque<ListNode> stack = new LinkedList<>();
        Deque<ListNode> stack2 = new LinkedList<>();
        while (temp1 != null) {
            stack.push(temp1);
            temp1 = temp1.next;
        }
        while (temp2 != null) {
            stack2.push(temp2);
            temp2 = temp2.next;
        }

        ListNode pop1 = stack.pop();
        ListNode pop2 = stack2.pop();
        while (pop1 != null && pop1 == pop2) {
            intersection = pop1;
            if (stack.size() == 0 || stack2.size() == 0) {
                break;
            }
            pop1 = stack.pop();
            pop2 = stack2.pop();
        }
        return intersection;
    }*/

    /**
     * 使用了大佬的双指针解法
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node1 = headA;
        ListNode node2 = headB;

        while (node1 != node2) {
            node1 = node1 == null ? headB : node1.next;
            node2 = node2 == null ? headA : node2.next;
        }
        return node1;

    }
}
